#pragma once

#include<cstdio>
#include<iostream>
#include<stdexcept>
#include<string>
#include<vector>
#include"create_expression.h"
#include"graph.h"
#include"graph_tests.h"
#include"tarjan.h"

using namespace std;

int number_of_graphs_with_n_vertices(int n)
{
	int answer = 1;
	for (int degree = 1; degree <= n*(n - 1); ++degree)
		answer *= 2;
	return answer;
}

void next_matrix(vector<vector<int>>* adjancy_matrix)
{
	int i = 0, j = 1, matrix_size = adjancy_matrix->size();
	while (i < matrix_size && j < matrix_size && (*adjancy_matrix)[i][j] == 1)
	{
		(*adjancy_matrix)[i][j] = 0;
		++j;
		if (i == j)
			++j;
		if (j >= matrix_size)
		{
			j = 0;
			++i;
		}
	}
	if (i < matrix_size && j < matrix_size)
		(*adjancy_matrix)[i][j] = 1;
	return;
}

void get_reachable_matrix(vector<vector<int> >* adjancy_matrix)
{
	int vertices_number = adjancy_matrix->size();
	for (int vertex1 = 0; vertex1 < vertices_number; ++vertex1)
		for (int vertex2 = 0; vertex2 < vertices_number; ++vertex2)
			for (int vertex3 = 0; vertex3 < vertices_number; ++vertex3)
				if ((*adjancy_matrix)[vertex2][vertex1] == 1 && (*adjancy_matrix)[vertex1][vertex3] == 1)
					(*adjancy_matrix)[vertex2][vertex3] = 1;
	return;
}

void check_get_components(const IGraph* graph, vector<vector<int> >& adjancy_matrix, const string& graphname)
{
	vector<int> component = get_strongly_connected_components(graph);
	vector<vector<int> > reachable_matrix = adjancy_matrix;
	get_reachable_matrix(&reachable_matrix);
	int vertices_number = graph->get_vertices_number();
	for (int vertex1 = 0; vertex1 < vertices_number; ++vertex1)
		for (int vertex2 = 0; vertex2 < vertices_number; ++vertex2)
			if (vertex1 != vertex2)
			{
				if (component[vertex1] > component[vertex2] && reachable_matrix[vertex1][vertex2] == 1)
					throw logic_error(graphname + " GRAPH: wrong sequence of components.");
				if (component[vertex1] == component[vertex2] && reachable_matrix[vertex1][vertex2] == 0)
					throw logic_error(graphname + " GRAPH: component was found incorrectly.");
			}
	return;
}

void test_get_components_on_small_graphs()
{
	for (int vertices_number = 0; vertices_number <= 5 ; ++vertices_number)
	{
		int number_of_graphs = number_of_graphs_with_n_vertices(vertices_number);
		vector<int> empty(vertices_number, 0);
		vector<vector<int>> adjancy_matrix(vertices_number, empty);
		for (int number_of_graph = 0; number_of_graph < number_of_graphs; ++number_of_graph)
		{
			IGraph* graph = make_compact_graph_from_matrix(adjancy_matrix);
			check_get_components(graph, adjancy_matrix, "SMALL");
			next_matrix(&adjancy_matrix);
			delete graph;
		}
	}
	cout<<"Tarjan algorithm is correct on small graphs.\n";
	return;
}

vector<vector<int> > incidence_list_to_adjancy_matrix(int vertices_number, const vector<pair<int, int> >& incidence_list)
{
	vector<int> empty(vertices_number, 0);
	vector<vector<int> > adjancy_matrix(vertices_number, empty);
	for (int i = 0; i < incidence_list.size(); ++i)
	{
		pair<int, int> edge = incidence_list[i];
		adjancy_matrix[edge.first][edge.second] = 1;
	}
	return adjancy_matrix;
}

void test_get_components_on_random_graphs()
{
	int vertices_number = 100;
	for (int graph_type = 0; graph_type < NUMBER_OF_GRAPH_TYPES; ++graph_type)
	{
		vector<pair<int, int> > edges = get_edges_for_graph_by_type(vertices_number, graph_type);
		IGraph* graph = make_compact_graph(vertices_number, edges);
		check_get_components(graph, incidence_list_to_adjancy_matrix(vertices_number, edges), graph_name(graph_type));
		delete graph;
	}
	int number_of_tests = 100;
	for (int test = 0; test < number_of_tests; ++test)
	{
		int edges_number = (rand() % vertices_number) * (rand() % vertices_number);
		vector<pair<int, int> > edges = get_distinct_edges_for_random_graph(vertices_number, edges_number);
		IGraph* graph = make_compact_graph(vertices_number, edges);
		check_get_components(graph, incidence_list_to_adjancy_matrix(vertices_number, edges), "RANDOM");
		delete graph;
	}
	cout<<"Tarjan algorithm is correct on random graphs.\n";
	return;
}

vector<pair<int, int> > renumber_edges(const vector<pair<int, int> >& original_edges, const vector<int>& shuffled_vertices)
{
	vector<pair<int, int> > renumbered_edges;
	for (int i = 0; i < original_edges.size(); ++i)
	{
		pair<int, int> edge = original_edges[i];
		pair<int, int> renumbered_edge(shuffled_vertices[edge.first], shuffled_vertices[edge.second]);
		renumbered_edges.push_back(renumbered_edge);
	}
	return renumbered_edges;
}

void check_get_components_of_renumbered_graph(const vector<pair<int, int> >& original_edges, const vector<int>& shuffled_vertices)
{
	int vertices_number = shuffled_vertices.size();
	IGraph* original_graph = make_compact_graph(vertices_number, original_edges);
	vector<int> original_component = get_strongly_connected_components(original_graph);
	IGraph* renumbered_graph = make_compact_graph(vertices_number, renumber_edges(original_edges, shuffled_vertices));
	vector<int> renumbered_component = get_strongly_connected_components(renumbered_graph);
	for (int vertex1 = 0; vertex1 < vertices_number; ++vertex1)
		for (int vertex2 = 0; vertex2 < vertices_number; ++vertex2)
		{
			if ((original_component[vertex1] == original_component[vertex2]) !=
				(renumbered_component[shuffled_vertices[vertex1]] == renumbered_component[shuffled_vertices[vertex2]]))
				throw logic_error("get components of renumbered graphs: FAILED");
		}
	delete original_graph;
	delete renumbered_graph;
}

void test_get_components_of_renumbered_graph()
{
	int vertices_number = 100, number_of_tests = 100;
	for (int test = 0; test < number_of_tests; ++test)
	{
		int edges_number = (rand() % vertices_number) * (rand() % vertices_number);
		check_get_components_of_renumbered_graph(get_distinct_edges_for_random_graph(vertices_number, edges_number),
												  get_shuffled_vertices(vertices_number));
	}
	cout<<"Tarjan algorithm remains correct after renumbering.\n";
	return;
}

vector<int> get_random_components(int vertices_number)
{
	vector<int> component;
	for (int vertex = 0; vertex < vertices_number; ++vertex)
		component.push_back(rand() % vertices_number);
	return component;
}

void check_condensate_graph(int vertices_number, vector<pair<int, int> > edges, const string& mode)
{
	IGraph* graph = make_compact_graph(vertices_number, edges);
	vector<int> component;
	if (mode == "RANDOM")
		component = get_random_components(vertices_number);
	if (mode == "STRONGLY CONNECTED")
		component = get_strongly_connected_components(graph);
	IGraph* condensated_graph = condensate_graph(graph, component);
	for (int i = 0; i < edges.size(); ++i)
	{
		pair<int, int> edge = edges[i];
		if (component[edge.first] != component[edge.second] && !condensated_graph->is_edge(component[edge.first], component[edge.second]))
			throw logic_error("condensate graph: FAILED.");
	}
	delete graph;
	delete condensated_graph;
	return;
}

void test_condensate_graph()
{
	int vertices_number = 100, number_of_tests = 100;
	for (int test = 0; test < number_of_tests; ++test)
	{
		int edges_number = (rand() % vertices_number) * (rand() % vertices_number);
		check_condensate_graph(vertices_number, get_distinct_edges_for_random_graph(vertices_number, edges_number), "RANDOM");
		check_condensate_graph(vertices_number, get_distinct_edges_for_random_graph(vertices_number, edges_number), "STRONGLY CONNECTED");
	}
	cout<<"Graph condensation is correct.\n";
	return;
}

void check_make_graph_from_expression(int variables_number, const vector<pair<int, int> >& disjuncts)
{
	IGraph* graph = make_graph_from_expression(variables_number, disjuncts);
	if (graph->get_vertices_number() != 2 * variables_number)
		throw logic_error("make graph from expression: wrong number of vertices.");
	if (graph->get_edges_number() != 2 * disjuncts.size())
		throw logic_error("make graph from expression: wrong number of edges.");
	for (int i = 0; i < disjuncts.size(); ++i)
	{
		int variable1 = disjuncts[i].first, variable2 = disjuncts[i].second;
		if (! graph->is_edge(variable_to_vertex(-variable1, variables_number), variable_to_vertex(variable2, variables_number)))
			throw logic_error("make graph from expression: FAILED.");
		if (! graph->is_edge(variable_to_vertex(-variable2, variables_number), variable_to_vertex(variable1, variables_number)))
			throw logic_error("make graph from expression: FAILED.");
	}
	delete graph;
	return;
}

void test_make_graph_from_expression()
{
	int variables_number = 1000, number_of_tests = 100;
	for (int test = 0; test < number_of_tests; ++test)
	{
		check_make_graph_from_expression(variables_number, get_expression_without_solution(variables_number));
		check_make_graph_from_expression(variables_number, get_expression_with_solution(variables_number));
	}
	cout<<"Make graph from expression is correct.\n";
	return;
}

void check_solve_2_sat_without_solution(int variables_number, const vector<pair<int, int> >& disjuncts)
{
	bool is_solution = (solve_2_sat(variables_number, disjuncts)).first;
	if (is_solution)
		throw logic_error("solve 2 sat found a solution of an expression without any solution.");
}

void test_solve_2_sat_without_solution()
{
	int variables_number = 1000, number_of_tests = 100;
	for (int test = 0; test < number_of_tests; ++test)
	{
		check_solve_2_sat_without_solution(variables_number, get_expression_without_solution(variables_number));
	}
	cout<<"Solve 2 sat is correct on graphs without solution.\n";
	return;
}

int sgn(int a)
{
	if (a > 0)
		return 1;
	if (a < 0)
		return -1;
	return 0;
}

void check_solve_2_sat_with_solution(int variables_number, const vector<pair<int, int> >& disjuncts)
{
	pair<bool, vector<int> > result = solve_2_sat(variables_number, disjuncts);
	bool is_solution = result.first;
	if (! is_solution)
		throw logic_error("solve 2 sat did not find a solution of an expression with a solution.");
	vector<int> solution = result.second;
	for (int i = 0; i < disjuncts.size(); ++i)
	{
		if (solution[abs(disjuncts[i].first)] != sgn(disjuncts[i].first) && solution[abs(disjuncts[i].second)] != sgn(disjuncts[i].second))
			throw logic_error("solve 2 sat found wrong solution.");
	}
}

void test_solve_2_sat_with_solution()
{
	int variables_number = 1000, number_of_tests = 100;
	for (int test = 0; test < number_of_tests; ++test)
	{
		check_solve_2_sat_with_solution(variables_number, get_expression_with_solution(variables_number));
	}
	cout<<"Solve 2 sat is correct on graphs with solution.\n";
	return;
}